package com.chb.link;

import com.sun.org.apache.xpath.internal.operations.Bool;

/**
 * 单链表
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        Node2 n1 = new Node2(1, "a", "a");
        Node2 n2 = new Node2(2, "b", "b");
        Node2 n3 = new Node2(3, "c", "c");
        Node2 n4 = new Node2(4, "d", "d");

        // 创建链表
        DoubleLinkedList list = new DoubleLinkedList();
        list.addNodeByOrder(n1);
        list.addNodeByOrder(n3);
        list.addNodeByOrder(n2); // 顺序插入测试
        list.addNodeByOrder(n4);
        list.showLinkedList();

        // 插入重复节点
        list.addNodeByOrder(n4);
        list.showLinkedList();

        // 修改节点
        System.out.println("修改节点");
        Node2 n4u = new Node2(4, "du", "du");
        list.updateNode(n4u);
        list.showLinkedList();

        // 删除节点
        System.out.println("删除节点");
        Node2 n4d = new Node2(4, "du", "du");
        list.delNode(n4d);
        list.showLinkedList();
        System.out.println("删除中间节点");
        Node2 n2d = new Node2(2, "b", "b");
        list.delNode(n2d);
        list.showLinkedList();
        list.delNode(n2d); // 重复删除

        System.out.println("链表长度：" + list.size());

        System.out.println("倒数第1个元素：" + list.findLastKNode(1));
        System.out.println("倒数第2个元素：" + list.findLastKNode(2));

        System.out.println("revert list");
        list.showLinkedList();
        list.addNodeByOrder(n1);
        list.addNodeByOrder(n3);
        list.addNodeByOrder(n2); // 顺序插入测试
        list.addNodeByOrder(n4);
        System.out.println();
        list.showLinkedList();
        list.revert();
        list.showLinkedList();

    }
}

class DoubleLinkedList {
    // 初始一个头结点
    private Node2 headNode2 = new Node2(0, "head", "head");


    // 翻转双向链表
    public void revert() {
        if (headNode2.getNext() == null || headNode2.getNext().getNext() == null) {
            return;
        }
        Node2 cur = headNode2.getNext();
        Node2 next = null;
        Node2 newHeadNode2 = new Node2(0, "head", "head");

        while (cur != null) {
            next = cur.getNext();

            cur.setNext(newHeadNode2.getNext());
            cur.setPre(newHeadNode2);
            if (newHeadNode2.getNext() != null) {
                newHeadNode2.getNext().setPre(cur);
            }
            newHeadNode2.setNext(cur);
            System.out.println(cur);

            cur = next;

        }
        headNode2.setNext(newHeadNode2.getNext());
    }

    // 寻找倒数第k个元素
    // 本文中是有头结点的链表，     leetCode中是无头结点的链表   https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/submissions/
    public Node2 findLastKNode(int k) {
        if (headNode2.getNext() == null) return null;

        // 长度不符合
        if (size() < k) return null;

        Node2 tmp = headNode2.getNext();
        for (int i = 0; i < size() - k; i++) {
            tmp = tmp.getNext();
        }
        return tmp;
    }

    // 链表长度
    public int size() {
        if (headNode2.getNext() == null) {
            return 0;
        }
        Node2 tmp = headNode2.getNext();
        int size = 0;
        while (tmp != null) {
            size++;
            tmp = tmp.getNext();
        }
        return size;
    }

    // 注意此处是单链表， 需要通过找到待删除节点的前一个节点， 通过tmp.next = tmp.next.next将节点删除
    public void delNode(Node2 node2) {
        Node2 tmp = headNode2;
        Boolean isFind = false;
        while (true) {
            if (tmp == null) {
                break;
            } else {
                if (tmp.getId() == node2.getId()) {
                    isFind = true;
                    break;
                }
                tmp = tmp.getNext();
            }
        }
        if (isFind) {
            // 自我删除
            tmp.getPre().setNext(tmp.getNext());
            if (tmp.getNext() != null) { // 注意如果带删除的节点是尾结点，就不需要修改
                tmp.getNext().setPre(tmp.getPre());
            }

        } else {
            System.out.println("没有找到" + node2);
        }
    }

    // https://leetcode-cn.com/problems/delete-middle-node-lcci/submissions/
    // 注意不可以是尾部节点
    public void delNode2(Node2 node2) {
        Node2 tmp = headNode2.getNext(); // 由于双向链表可以自我删除，只要找到待删除节点即可
        Boolean isFind = false;
        while (true) {
            if (tmp == null) {
                break;
            } else {
                if (tmp.getId() == node2.getId()) {
                    isFind = true;
                    break;
                }
                tmp = tmp.getNext();
            }
        }
        if (isFind) {
            if (tmp.getNext() == null) {
                tmp = null;
            } else {
                tmp.setId(tmp.getNext().getId());
                tmp.setName(tmp.getNext().getName());
                tmp.setNickname(tmp.getNext().getNickname());
                tmp.setNext(tmp.getNext().getNext());
            }
        } else {
            System.out.print("没有找到" + node2);
        }
    }

    public void updateNode(Node2 node2) {
        Node2 tmp = headNode2;
        Boolean isFind = false;
        while (true) {
            if (tmp == null) {
                break;
            } else {
                if (tmp.getId() == node2.getId()) {
                    isFind = true;
                    break;
                }
                tmp = tmp.getNext();
            }
        }
        if (isFind) {
            tmp.setName(node2.getName());
            tmp.setNickname(node2.getNickname());
        } else {
            System.out.print("没有找到" + node2);
        }
    }


    public void addNode(Node2 node2) {
        Node2 temp = headNode2;

        // 从头结点开始向后遍历，找到最后一个节点
        while (true) {
            if (temp.getNext() == null) {
                node2.setPre(temp);
                temp.setNext(node2);
                break;
            }
            temp = temp.getNext();
        }
    }

    public void addNodeByOrder(Node2 node2) {
        Node2 temp = headNode2;

        Boolean isFind = false;
        while (true) {
            if (temp.getNext() == null) {
                break;
            } else {
                if (temp.getNext().getId() > node2.getId()) {
                    isFind = true;
                    break;
                } else if (temp.getNext().getId() == node2.getId()) {
                    System.out.println("node " + node2.getId() + " 已经添加");
                    break;
                }
            }
            temp = temp.getNext();
        }
        if (isFind) { // 中间节点
            node2.setNext(temp.getNext());
            node2.setPre(temp);
            temp.getNext().setPre(node2);
            temp.setNext(node2);
        } else {
            if (temp.getNext() == null) { // 插到尾结点
                temp.setNext(node2);
                node2.setPre(temp);
            }
        }
    }

    // 打印链表
    public void showLinkedList() {
        System.out.println("show linkedlist start...");
        if (headNode2.getNext() == null) {
            System.out.println("链表为空。。。");
            return;
        }
        Node2 tmp = headNode2;
        while (true) {
            if (tmp == null) {
                break;
            }
            System.out.println(tmp + ", preNode = " + tmp.getPre() + ", nextNode = " + tmp.getNext());
            tmp = tmp.getNext();
        }
        System.out.println("show linkedlist end...");
    }

}

class Node2 {
    private int id;
    private String name;
    private String nickname;
    private Node2 pre;  // 指向前一个节点
    private Node2 next; // 指向下一个节点

    public Node2(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickname() {
        return nickname;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }

    public Node2 getNext() {
        return next;
    }

    public void setNext(Node2 next) {
        this.next = next;
    }

    public Node2 getPre() {
        return pre;
    }

    public void setPre(Node2 pre) {
        this.pre = pre;
    }

}